package DynamicProgramming;//给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
//
// 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子
//序列。 
// 
//
// 示例 1： 
//
// 
//输入：nums = [10,9,2,5,3,7,101,18]
//输出：4
//解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,1,0,3,2,3]
//输出：4
// 
//
// 示例 3： 
//
// 
//输入：nums = [7,7,7,7,7,7,7]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 2500 
// -10⁴ <= nums[i] <= 10⁴ 
// 
//
// 
//
// 进阶： 
//
// 
// 你能将算法的时间复杂度降低到 O(n log(n)) 吗? 
// 
// Related Topics 数组 二分查找 动态规划 👍 2408 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class lengthOfLIS {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if(len<2){
            return len;
        }
        //动态规划,dp[i]表示到达当前位置时的递增长度
        int[] dp = new int[len];
        dp[0] = 1;
        for(int i=1;i<len;i++){
            int num = 0;
            //每次从前边的找比当前值小的值 的dp值中的最大值+1，找不到则初始化为1
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    num = Math.max(dp[j],num); //取最大值
                }
            }
            //为0说明前面没有比它小的,置为1
            dp[i] = num==0 ? 1 : num+1;
        }
        System.out.println(Arrays.toString(dp));
        int max = Arrays.stream(dp).max().getAsInt(); //输出最大的递增序列长度
        return max;
    }

    public static int lengthOfLIS1(int[] nums) {
        int len = 1, n = nums.length;
        if (n < 2) {
            return n;
        }
        int[] d = new int[n + 1];
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            //如果当前数比递增数组的尾值大，直接添加到它末尾。
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                //否则利用二分法找到当前值应该在递增数组中的位置,并覆盖
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
            System.out.println(Arrays.toString(d));
            System.out.println(len);
        }

        return len;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
